The present invention relates to manufacturing and, more particularly, to the ordering of manufacturing jobs having sequence-dependent set-up times.
The advent of automated stations for manufacturing products, i.e. flexible manufacturing systems (FMS), has provided for the rapid and accurate assembly of a wide selection of products. In fact, the assembly process can be so rapid that the time required in setting up a particular FMS machine for its next product run can account for most of the total production time. As an example, an automated tooling machine, capable of milling, shaping and drilling materials such as metal into final pieces, requires the proper tools to be in place before its next run. Both transfer and fine-adjustment of the particular tool "palette" required by the FMS machine consume time otherwise available for production, thus increasing costs and time to delivery. Due to the relatively large capital investment in FMS machines, loss of production time becomes a particularly acute problem.
The problem of minimizing set-up times in an FMS environment can be illustrated in the context of automated printed circuit board (PCB) loading machines. These machines automatically place electrical components onto printed circuit boards by following computer instructions. A typical machine holds 100 different components out of a total inventory of 500 or more. While each PCB to be manufactured may typically require only 10 to 70 of these components, the mix of components required for different PCB types can be partially or completely different. Setting up the automated PCB loading machine with a new set of components for the next PCB run consumes precious production time. In a production environment comprising a high mixture of different PCB (or other product) types, each type produced in low volume, the set-up times between jobs can account for 60-70% of total production time.
The fundamental FMS scheduling problem reduces to that of ordering jobs in an optimal sequence such that swapping of required resources is minimized. For an automated tooling machine, this reduces the number of tool changes required for a sequence of jobs. For a PCB loading machine, one seeks to minimize the number of component swaps required. In any automated flexible manufacturing environment, the problem may be formulated exactly the same way: the manufacturing planner seeks to minimize the time used in sequentially reconfiguring a manufacturing system for a series of different jobs.
Except for the simplest of systems, the typical FMS scheduling problem defies closed-form solution. The number of variables and resultant equations involved makes an optimal solution extremely time-consuming if possible at all. Calculating all possible job sequences and ranking them by the number of tool or component switches required likewise remains highly inefficient. In both cases, the computations may not conclude before the production day has passed. To provide a useful solution in a practical period of time, planners require some form of heuristic or approximation algorithm.
One proposed heuristic for solving the FMS scheduling problem attempts to solve the linear programming problem using Lagrange relaxation techniques. Bard, J., "A Heuristic for Minimizing the Number of Tool Switches on a Flexible Machine", IIE Transactions, December 1988, pp. 382-391. In essence, the Lagrangian technique relaxes certain requirements of the formal sequencing problem in order to solve a simpler but inexact set of equations. The technique yields a collection of potentially feasible solutions. The heuristic then makes small changes or perturbations to each of the possible solutions to find a solution which has both a low number of reconfigurations and for which any small alteration of sequence causes the number of tool switches only to increase. The "solution" found through this heuristic represents a local minimum, in the sense that small excursions from the resulting sequence only increase the set-up time. The heuristic, however, provides little guarantee that the resultant sequence is in fact a globally optimal solution for the problem. In addition, despite implementing a simpler set of equations, the results shown in the Bard paper apply only to very simple FMS environments. FMS machines often involve a far greater number of component or tool locations and a greater number of tools/components in inventory, rendering even the reduced set of equations unmanageable for computation.
Another approach to the FMS sequencing problem compares it to the familiar traveling salesman problem (TSP). The classical TSP stipulates that a salesperson must visit a sequence of cities one at a time, never visiting a city twice. The constraint applied to the sequence is that it minimize the total distance travelled. The FMS sequencing problem may be compared to the classical TSP if each city represents a batch of identical PCBs to be manufactured and the travel distance between cities represents the number of tool switches required between PCB batches. The FMS problem is not in fact identical to the classical traveling salesman problem because the distances between the PCB "cities" depend upon those PCBs already manufactured. In other words, the FMS machine constantly changes its configuration state, varying the number of component switches required for the next job. Clearly, the dynamic FMS problem is far more difficult than the classical static traveling salesman problem. If the classical traveling salesman problem is then a "static" problem (TSP-S), with constant distances between cities, the FMS sequencing problem is a "dynamic" TSP, or TSP-D, where inter-city distances lengthen or decrease depending on where the salesperson (i.e. FMS machine) has already been.
One method of solving the flexible manufacturing sequencing problem, first cast as a dynamic traveling salesman problem, solves a related static traveling salesman problem to arrive at a potential set of likely sequence candidates, as disclosed for example by Tang, C. and Denardo, E. in "Models Arising from a Flexible Manufacturing Machine, Part I: Minimization of the Number of Tool Switches", Operations Research, Vol. 36, No. 5, pp. 767-777, 1988. Tang and Denardo use the minimum number of component or tool switches between any given pair of jobs as the inter-city length for the static TSP. The problem is solved by minimizing the total distance (here, the total number of tool/component switches) for the entire sequence of jobs. After arriving at one or more potential sequence candidates, the method determines exactly how many tool switches are in fact used and ranks sequences by their numbers of switches: the sequence with the lowest number is selected.
Tang and Denardo's heuristic for solving the flexible manufacturing sequence problem involves several serious limitations. The most complex job environment described for test data comprised a tool-inventory of 30 tools, a machine capable of holding 15 of the tools and a set of 40 jobs. However, FMS machines, such as the PCB loading system described above, can hold around 100 components, selected from inventories often greater than 500 components. Confronted with complex FMS environments and large component inventories, Tang and Denardo's method does not converge adequately to a sequence solution. In addition, in implementing any sequencing algorithm one desires at least a rough measure of how far the solution remains from optimality. Tang and Denardo provide no theoretical lower bound on optimality with which to compare the results of their heuristic. Applied to complex manufacturing sequencing problems, one might never discover whether great improvement has been accomplished or not using Tang and Denardo's procedure.
What is needed is an improved method and system for choosing sequences of jobs on flexible manufacturing systems. The method and system should account for the complexities of actual manufacturing environments. More specifically, the method should allow for large numbers of tools and components, of which only a small portion are selected for any given job. In addition, the method should demonstrate a high likelihood of converging upon a globally optimal solution to the sequencing problem in a reasonable time using affordable computational resources. Furthermore, the method should provide some estimate of how inferior the solution remains from optimum.